// 41.缺失的第一个正数
package Leetcode_Second_Brush;

public class Solution041 {
    public int firstMissingPositive(int[] nums) {
        // 缺失的第一个正数的范围一定在 1 ~ nums.length + 1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0)
                nums[i] = nums.length + 1;
        }

        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i]) <= nums.length)
                nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0)
                return i + 1;
        }
        return nums.length + 1;
    }
}
